package test.algos.sorting.mergesort;

import java.util.ArrayList;
import java.util.List;

import test.algos.sorting.SortUtil;

public class MergeStep {

	private List<Integer> inputData;

	private int subListSize;

	public MergeStep(int subListSize, List<Integer> inputData) {

		this.inputData = inputData;
		this.subListSize = subListSize;

	}

	public MergeOutput<Integer> merge() {

		int noOfSublists = computeNoOfLists();

		List<Integer> outputList = new ArrayList<>();
		
		MergeOutput<Integer> mergeOutput = new MergeOutput<>();

		for (int i = 0; i < noOfSublists; i += 2) {

			int curElemIndex = i * subListSize;

			List<Integer> subList1 = (List<Integer>) SortUtil.safeGetSublist(
					inputData, curElemIndex, curElemIndex + subListSize);
			List<Integer> subList2 = (List<Integer>) SortUtil.safeGetSublist(
					inputData, curElemIndex + subListSize, curElemIndex + 2
							* subListSize);
			
			MergeOutput<Integer> mergeSubOutput = merge(subList1, subList2);

			outputList.addAll(mergeSubOutput.getSortedList());
			computeInversionCount(mergeOutput, mergeSubOutput.getInversionCount());

		}

		mergeOutput.setSortedList(outputList);
		return mergeOutput;

	}

	private MergeOutput<Integer> merge(List<Integer> subList1,
			List<Integer> subList2) {

		int combListSize = subList1.size() + subList2.size();

		MergeOutput<Integer> mergeOutput = new MergeOutput<>();

		List<Integer> outputList = new ArrayList<>();

		int leftListInex = 0;
		int rightListIndex = 0;

		for (int i = 0; i < combListSize; i++) {

			Integer leftElem = SortUtil.safeGet(subList1, leftListInex);
			Integer rightElem = SortUtil.safeGet(subList2, rightListIndex);

			Integer compareValue = SortUtil.compareAndReturn(leftElem,
					rightElem);

			if (compareValue != null) {
				if (compareValue > 0) {
					outputList.add(rightElem);
					rightListIndex++;
					computeInversionCount(mergeOutput,
							(subList1.size() - leftListInex));
				} else if (compareValue < 0) {
					outputList.add(leftElem);
					leftListInex++;
				} else {
					outputList.add(leftElem);
					outputList.add(leftElem);
					rightListIndex++;
					leftListInex++;
				}
			}

		}

		mergeOutput.setSortedList(outputList);
		return mergeOutput;

	}

	private int computeNoOfLists() {

		return (int) (Math.ceil((double) inputData.size() / subListSize));

	}

	private void computeInversionCount(MergeOutput<Integer> mergeOutput,
			Integer invCount) {
		
		if(invCount == null){
			return;
		}

		Integer curInvCount = mergeOutput.getInversionCount();

		if (curInvCount != null) {
			mergeOutput.setInversionCount(curInvCount + invCount);
		} else {
			mergeOutput.setInversionCount(invCount);
		}

	}

}
